/**
 * Created by L.jp
 * Description:KMP算法代码实现
 * User: 86189
 * Date: 2021-12-10
 * Time: 22:38
 */
public class Algorithm {
    //首先给出暴力（BF)算法代码
    /*
    public static int bf(String str,String sub){
        int strLen=str.length();
        int subLen=sub.length();
        if(str==null || sub==null){
            return -1;
        }
        if(strLen==0|| subLen==0){
            return -1;
        }
        int i=0;
        int j=0;
        while(i<strLen && j<subLen){
            if(str.charAt(i)==sub.charAt(j)){
                i++;
                j++;
            }else{
                i=i-j+1;//匹配失败i就要回退到上一次匹配位置开始的下一个坐标
                j=0;//j回退到0
            }
        }
        if(j>=subLen){
            return i-j;//如果j走到了大于等于子串的长度的位置，那么说明匹配成功，需要返回子串在主串出现的起始位置
        }
        return -1;

    }

     */

    //对于KMP算法则不一样，原则只有一个，当匹配失败时，i不需要回退，j也不需要每次回退到0位置
    // 而是回退的一个特定的位置，而这个特定的位置需要用一个函数来求，我们利用next数组保存当每一个j下标字母匹配失败时返回的位置
    /**
     * @param str: 主串
     * @param sub: 子串
     * @param pos: 从主串的pos位置开始匹配
     * [str, sub, pos]
     * @return int      返回子串与主串匹配成功时，第一次出现的起始位置
     * @description TODO
     */
    public static int  kmp(String str,String sub,int pos){//pos表示主串从pos位置开始匹配/搜索子串
        int strLen=str.length();
        int subLen=sub.length();
        if(str==null || sub==null) return -1;
        if(strLen==0 || subLen==0) return -1;
        int i=pos;//从给定的位置开始匹配
        int j=0;
        int[] next=new int[subLen+1];//创建next数组表示子串匹配失败后，j需要回退的位置，next数组最短长度为2，防止有“a","a"的情况
        getNext(next,sub);//根据子串构造好next数组
        while(i<strLen && j<subLen){
            if(j==-1 ||str.charAt(i)==sub.charAt(j)){//如果j==-1表示一开始就匹配失败，这种情况也要重新让j++,从0开始匹配
                i++;
                j++;
            }else{
                j=next[j];//当i下标字符和j下标字符不相等时，那么i不需要回退，j需要回退到指定位置，这个指定位置直接从next数组取，前面已经构造好next数组
            }
        }
        if(j>=subLen){
            return i-j;//匹配成功，返回子串在主串中出现的起始位置
        }
        return -1;//匹配失败
    }

    /**
     * @param next: //存储子串每一个位置匹配失败后回退的位置
     * @param sub: 子串
     * [next, sub]
     * @return void
     * @description TODO
     */
    //构造子串的next数组
    //KMP 的精髓就是 next 数组：也就是用 next[j] = k;来表示，不同的 j 来对应一个 K 值，这个K就是你将来要移动的j要移动的位置。

    //而 K 的值是这样求的：
    //1、规则：在子串中找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，叫做前缀表，另一个以 j-1下标字符结尾，叫做后缀表
    //2、那么这个K就是两个相等的真子串的长度，也可以说是两个相等的前缀后缀表的长度，也代表了当j位置匹配失败时要回退到的位置
    //2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始；

    /*这里我们就可以得出一些结论：
    首先假设next[j]==k这个条件成立，我们可以推出sub[0]...sub[k-1]==sub[i-k]...sub[i-1]，表示这两个区间的字符串是相等的，也就是前面说的两个相等的真子串
    那么也就是说sub[j-1]==sub[k-1],那么我们怎么样根据next[j]=k去求出next[j+1]的值呢？
    那么我们还可以假设sub[j]==sub[k],那么也就是说可以得出sub[0]...sub[k]==sub[i-k]...sub[i],这两个区间的字符串相等，得出next[j+1]=k+1,这个结论跟我们手动推导的是一样的
    也就是这个是成立的。
    对应到题目中，我们要求当前j位置的回退位置，因为我们是从j=2开始计算的，所以需要利用前一个的k值来求得，也就是当sub.charAt(j-1)==sub.charAt(k)时，next[j]=k+1;
    当sub[j]！=sub[k]的时候我们只需要让k一直回退直到他们相等就可以直接利用上面的公式计算，不相等时k=next[k];
     */
    public static void getNext(int[] next,String sub){
        //初始化，注意有的题目中第一个是0，第二个是1，所以我们只要明白了求next数组的方法，那么以后在求next数组的时候，可以根据题目要求加以变换
        next[0]=-1;
        next[1]=0;
        //因为0和1下标的next值已经构造好，所以j从2开始构造
        int j=2;//下一项，这个表示我的j已经先走了一步
        int k=0;//k表示j下标匹配失败后需要回退的位置，表示前一项的k
        while(j<sub.length()){//从2位置开始求每个位置匹配失败时需要回退的位置
            //这个时候j回退的位置是不确定的，我们需要根据j-1的k来计算，如果j-1的字符跟k的字符一样，那么j的回退位置就是k+1
           if(k==-1 || sub.charAt(j-1)==sub.charAt(k)){//当sub[j-1]!=sub[k]时，k需要回退，有可能退到-1位置，那么这个时候j下标字符匹配只能从0开始，让k+1
               next[j]=k+1;
               j++;
               k++;
           }else{
               k=next[k];//k需要一直回退，直到sub[j-1]=sub[k]
           }
        }
    }

    public static void main(String[] args) {
        System.out.println(kmp("abcdabcabf","bcab",0));
        System.out.println(kmp("11221234","234",0));
        System.out.println(kmp("AABBCDEFGG","CD",0));

    }
    /*
    next数组还可以优化为nextval数组：
    在next数组的基础上，如果回退的位置的字符和当前字符一样，那么就回退到那么字符的next位置，如果不同就回退自己的next位置
    模式串 t=‘abcaabbcabcaabdab’
    该模式串的 next 数组的值为 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
          nextval 数组的值为 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
          这里是在我们推导的公式上加了一个1
     */

}
